# Nikhil Ketkar, Fri Feb 15 21:56:37 PST 2008

import sys
import random

class Graph(object):
    def __init__(self, vertex_count, edge_count, vertex_label_count, edge_label_count):        
        self.vertex_count = vertex_count
        self.edge_count = edge_count
        self.vertex_label_count = vertex_label_count
        self.edge_label_count = edge_label_count
        self.vertices = {}
        self.edges = {} 
        self.create_vertices()
        self.create_backbone()
        self.add_random_edges()

    def add_vertex(self, vertex_id, vertex_label):
        self.vertices[vertex_id] = vertex_label

    def add_edge(self, vertex1, vertex2, edge_label, replace):
        if vertex1 > vertex2:
            edge_index = (vertex1,vertex2)
        elif vertex2 > vertex1:
           edge_index = (vertex2, vertex1)
        else:
            return 1
        if not replace:
            if self.edges.has_key(edge_index):
                return 1
            else:
                self.edges[edge_index] = edge_label
                return 0
        else:
            self.edges[edge_index] = edge_label
            return 0            

    def create_vertices(self):
        for vertex in xrange(0, self.vertex_count):
            self.add_vertex(vertex + 1, random.randint(1, self.vertex_label_count))

    def create_backbone(self):
        for vertex in xrange(0, self.vertex_count - 1):
            self.add_edge(vertex + 1, vertex + 2, random.randint(1, self.edge_label_count), False)

    def add_random_edges(self):
        edges_to_add = self.edge_count - len(self.edges.keys())
        if edges_to_add > 0:
            for edge in xrange(0, edges_to_add):
                return_value = 0
                while return_value == 0:
                    return_value =  self.add_edge(random.randint(1, self.vertex_count),
                                                  random.randint(1, self.vertex_count),
                                                  random.randint(1, self.edge_label_count),
                                                  False) 

    def fuzz_vertices(self, vertex_fuzz):
        if vertex_fuzz > self.vertex_count:
            return 1
        for vertex in xrange(0, vertex_fuzz):
            curr_vertex = random.randint(1, self.vertex_count + 1)
            self.vertices[curr_vertex] = random.randint(1, self.vertex_label_count)
        return 0

    def fuzz_edges(self, edge_fuzz):
        if edge_fuzz > self.edge_count:
            return 1
        edge_indices = self.edges.keys()
        for edge in xrange(0, edge_fuzz):
            curr_edge = edge_indices[random.randint(0, self.edge_count - 1)]
            self.edges[curr_edge] = random.randint(1, self.edge_label_count)
        return 0
        
    def merge(self, merge_graph):
        for vertex in xrange(0,merge_graph.vertex_count):
            self.add_vertex(vertex+1, merge_graph.vertices[vertex+1])
        for edge in merge_graph.edges.keys():
            self.add_edge(edge[0], edge[1], merge_graph.edges[edge], True)
        
    def subdue_print(self, class_label, output):
        output.write(str(class_label + "\n"))
        for vertex in xrange(0, self.vertex_count): 
                     output.write("v")
                     output.write(" ")
                     output.write(str(vertex + 1))
                     output.write(" ")
                     output.write(str(self.vertices[vertex+1]))
                     output.write("\n")
        for edge in self.edges.keys():
                     output.write("u")
                     output.write(" ")
                     output.write(str(edge[0]))
                     output.write(" ")
                     output.write(str(edge[1]))
                     output.write(" ")
                     output.write(str(self.edges[edge]))
                     output.write("\n")

    def graphviz_print(self, output):
        output.write(str("graph G { \n"))
        for vertex in xrange(0, self.vertex_count): 
                     output.write(str(vertex + 1))
                     output.write(" [ label = \"")
                     output.write(str(self.vertices[vertex + 1]))
                     output.write("\" ];\n")
        for edge in self.edges.keys():
                     output.write(str(edge[0]))
                     output.write(" -- ")
                     output.write(str(edge[1]))
                     output.write(" [ label = \"")
                     output.write(str(self.edges[edge]))
                     output.write("\" ];\n")
        output.write(str("}\n"))

if __name__ == "__main__":
    
    print "---------- graph.py"
    
    print "---------- random.seed(\"abcde\")"
    random.seed("abcde")

    print "---------- g1 = Graph(4,4,3,3)"
    g1 = Graph(4,4,3,3)

    print "---------- g2 = Graph(5,5,5,5)"
    g2 = Graph(5,5,5,5)

    print "---------- g1.subdue_print(\"XP\", sys.stdout)"
    g1.subdue_print("XP", sys.stdout)

    print "---------- g1.graphviz_print(sys.stdout)"
    g1.graphviz_print(sys.stdout)

    print "---------- g2.subdue_print(\"XP\", sys.stdout)"
    g2.subdue_print("XP", sys.stdout)

    print "---------- g1.graphviz_print(sys.stdout)"
    g1.graphviz_print(sys.stdout)

    print "---------- g1.fuzz_vertices(2)"
    g1.fuzz_vertices(2)

    print "---------- g1.subdue_print(\"XP\", sys.stdout)"
    g1.subdue_print("XP", sys.stdout)

    print "---------- g1.graphviz_print(sys.stdout)"
    g1.graphviz_print(sys.stdout)

    print "---------- g1.fuzz_edges(2)"
    g1.fuzz_edges(2)

    print "---------- g1.subdue_print(\"XP\", sys.stdout)"
    g1.subdue_print("XP", sys.stdout)

    print "---------- g1.graphviz_print(sys.stdout)"
    g1.graphviz_print(sys.stdout)
    
    print "---------- g2.merge(g1)"
    g2.merge(g1)

    print "---------- g2.subdue_print(\"XP\",sys.stdout)"
    g2.subdue_print("XP",sys.stdout)

    print "---------- g1.graphviz_print(sys.stdout)"
    g1.graphviz_print(sys.stdout)
